import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;
import java.util.Collection;

/**
 * ContextTreeNode class represents a node in the context characteristics tree.  The context
 * characteristics tree represents how the set of contexts should be split up to achieve
 * the optimal encoding.
 * 
 * @author Yong Shin
 *
 */
public class ContextTreeNode {
        private boolean DEBUG = false;

	/** Left child node */
	private ContextTreeNode left;
	
	/** Right child node */
	private ContextTreeNode right;
	
	/** Tree Node label */
	private int label;
	
        /** Data in use at this node; only valid when this node is a leaf node.  */
        private ContextDataCollection data;
        
	/** Split criteria for the node */
	private SplitCriteria splitCrit;
        
        /** num leafnodes; initially set to -1; assigned with calcNumLeafnodes call 
        // currently numleafnodes set only once; if tree structure is modified afterwards, 
        // numleafnodes will be inaccurate. 
        // represents # of leafnodes (possibly including self). 
        */
        private int numleafnodes; 
        
        public int getNumLeafnodes() {
            if (numleafnodes == -1) {
              calcNumLeafnodes();
            }
            return numleafnodes;
        }

        /** returns number of leafnodes where SplitCriteria sc was used in some ancestor */
        public int getNumLeafnodesUsingCriteria(SplitCriteria sc) {
            if (sc.equals(splitCrit)) 
                return getNumLeafnodes();
            else { // this should work, but is inefficient, in that 
            // it searches branches where sc is no longer available. 
                int retval = 0;
                if (left != null)
                    retval += left.getNumLeafnodesUsingCriteria(sc);
                if (right != null)
                    retval += right.getNumLeafnodesUsingCriteria(sc);                    
                return retval;
            }
        }

        /** returns number of leafnodes where 
            splitting by sc results in one side of split
             having no data. Includes nodes where sc was used in some ancestor. */
        public int getNumUselessSplitLeafnodes(SplitCriteria sc) {
            if (sc.equals(splitCrit)) 
                return getNumLeafnodes();
            else if (left == null && right == null) {
            // leafnode, check split. 
                BitCounts[] bcounts = data.getBitCounts(sc.getContextID(), sc.getBucketID());			
			// check if either of the hypothetical split child nodes is empty
                if (bcounts[0].oneBits + bcounts[0].zeroBits == 0 || 
					bcounts[1].oneBits + bcounts[1].zeroBits == 0) 
                    return 1; 
                else return 0;
            }
            else { // search both halves; not efficient.
                int retval = 0; 
                    retval += left.getNumUselessSplitLeafnodes(sc);
                    retval += right.getNumUselessSplitLeafnodes(sc);                
                return retval;
            }

        }
        
        /** returns number of leafnodes where SplitCriteria sc is still 
            available  AND 
            where splitting by sc results in one side of split
             having no data.*/
        public int getNumAvailableUselessSplitLeafnodes(SplitCriteria sc) {
            if (sc.equals(splitCrit)) 
                return 0;
            else if (left == null && right == null) {
            // leafnode, check split. 
                BitCounts[] bcounts = data.getBitCounts(sc.getContextID(), sc.getBucketID());			
			// check if either of the hypothetical split child nodes is empty
                if (bcounts[0].oneBits + bcounts[0].zeroBits == 0 || 
					bcounts[1].oneBits + bcounts[1].zeroBits == 0) 
                    return 1; 
                else return 0;
            }
            else { 
                int retval = 0;            
                if (sc.getContextID() == splitCrit.getContextID()) {
                 // search only proper half.
                  if (splitCrit.compareTo(sc) > 0)  {
                       retval += left.getNumAvailableUselessSplitLeafnodes(sc);
                  }
                  else {
                       retval += right.getNumAvailableUselessSplitLeafnodes(sc);                
                  }
                }
                else { // search both halves. 
                    retval += left.getNumAvailableUselessSplitLeafnodes(sc);
                    retval += right.getNumAvailableUselessSplitLeafnodes(sc);                
                }
                return retval;
            }
        }
        
        private void calcNumLeafnodes() {
            if (left == null && right == null)
              numleafnodes = 1; 
            else {
              numleafnodes = 0;            
              if (left != null) 
                 numleafnodes +=  left.getNumLeafnodes();
              if (right != null)
                 numleafnodes +=  right.getNumLeafnodes();
            }
        }
	
	/**
	 * Contains split criteria that has not been used.
	 */
	private TreeSet<SplitCriteria> availableCriteria;
	
	public ContextTreeNode(TreeSet<SplitCriteria> availableCriteria, 
                               ContextDataCollection cdc) {
		this.availableCriteria = availableCriteria;
		label = -1;
                data = cdc;
                numleafnodes = -1;
	}
/*
	public ContextTreeNode(ContextTreeNode left, 
                               ContextTreeNode right, 
                               SplitCriteria splitCrit) {
		this.availableCriteria = null;
		label = -1;
                data = null;
                this.left= left;
                this.right = right;
                this.splitCrit = splitCrit;
	}
*/	

	/**
	 * Calculates the percentage of the part with respect to the whole.
	 * @param part
	 * @param whole
	 * @return
	 */
	private double percent(int part, int whole) {
		return Math.round(part * 1000.0 / whole)/10.0;
	}


// should call this with root node of tree. 
        public void printCriteriaUsageStats() {
           int totalleafnodes = getNumLeafnodes();
           int numCtx = ContextDefinition.getContextDefinition().getNumContexts();

           System.out.println("Criteria Usage stats, " + 
                                totalleafnodes  + " leafnodes total; [%usage %useless %availUseless]:");
                for (int i=0; i<numCtx; i++) {
                        Context ctx = ContextDefinition.getContextDefinition().getContext(i);
                        System.out.println("Context " + ctx.toString());
                        int numBuc = ctx.getNumberBuckets();
                        for (int j=0; j<numBuc-1; j++) {
                            SplitCriteria sc; 
                            sc = new SplitCriteria(ctx.getContextID(), j);
                            System.out.println("\t(" + (j+1) + ") " + 
                                        " [" + percent(getNumLeafnodesUsingCriteria(sc),totalleafnodes)
                                        + "% " + percent(getNumUselessSplitLeafnodes(sc),totalleafnodes)
                                        + "% " + percent(getNumAvailableUselessSplitLeafnodes(sc),totalleafnodes) + "%]");
                        }
                }
           
        }
        
        
	public ContextTreeNode getLeftChild() {
		return left;
	}
	
	public ContextTreeNode getRightChild() {
		return right;
	}
	
	public int getLabel() {
		return label;
	}
	
	public void setLabel(int label) {
		this.label = label;
	}
	
	public SplitCriteria getSplitCriteria() {
		return splitCrit;
	}
        
        public ContextDataCollection getData() {
            return data;
        }
        
        public BitCounts getCount() {
            return data.getTotal();
        }
	
	/**
	 * Split the node using split criteria.
	 * @param criteria
	 */
	@SuppressWarnings("unchecked")
	public void split(SplitCriteria criteria) {
		
		// save split criteria
		splitCrit = criteria;
                int currContextID = criteria.getContextID();
                int currBucketID = criteria.getBucketID();

                // split available into two lists. 
                TreeSet<SplitCriteria> leftCrit = new TreeSet<SplitCriteria>();
                TreeSet<SplitCriteria> rightCrit = new TreeSet<SplitCriteria>();

                for (SplitCriteria sc : availableCriteria) {
                    if (sc.getContextID() == currContextID) {
                        if (sc.getBucketID() < currBucketID) {
                            leftCrit.add(sc); 
                        }
                        else if (sc.getBucketID() > currBucketID) {
                            rightCrit.add(sc);
                        }
                    }
                    else { // nonmatching context ID crit belongs in both lists
                        leftCrit.add(sc);
                        rightCrit.add(sc);
                    }
                }
                
                if (DEBUG) {
                    System.out.println("Pre-split data:" + data);                    
                }
                // split data 
                ContextDataCollection leftData, rightData;
                rightData = data.split(currContextID, currBucketID);
                leftData = data;
                				
		// create child nodes
		left = new ContextTreeNode(leftCrit, leftData);
		right = new ContextTreeNode(rightCrit, rightData);

                if (DEBUG) {
                    System.out.println("Post-split data:" + data
                        + " left:" + left.data + " right:" + right.data);                    
                }
                
                
	}
	
	public Collection<SplitCriteria> getAvailableCriteria() {
		return availableCriteria;
	}
	
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append("num_avail_split_crit: ");
                if (availableCriteria != null) sb.append(availableCriteria.size() + ",");
                else sb.append("0,");
                sb.append(" bitCounts: " + getCount()  + "\n");
		if (left == null && right == null) {
			sb.append("has no child nodes\n");
		} else {
			sb.append("has child nodes\n");
			sb.append("label: " + label + "\n");
			sb.append("split criteria: " + splitCrit);
		}
		return sb.toString();
	}
}
